package com.congee02;

public class IsSameTree_Morris {

    public boolean isSameTree(TreeNode p, TreeNode q) {
        return morris(p, q);
    }

    public boolean morris(TreeNode root, TreeNode root1) {

        TreeNode cur = root;
        TreeNode cur1 = root1;

        while (cur != null && cur1 != null) {

            if (cur.val != cur1.val) {
                return false;
            }

            TreeNode mostRight = cur.left;
            TreeNode mostRight1 = cur1.left;

            if (mostRight == null && mostRight1 != mostRight) {
                return false;
            }

            if (mostRight != null && mostRight1 != null) {
                if (mostRight.val != mostRight1.val) {
                    return false;
                }
                while (mostRight.right != null && mostRight.right != cur) {
                    mostRight = mostRight.right;
                }
                while (mostRight1.right != null && mostRight1.right != cur1) {
                    mostRight1 = mostRight1.right;
                }
                if (mostRight.right == null) {
                    mostRight.right = cur;
                    cur = cur.left;
                } else {
                    mostRight.right = null;
                    cur = cur.right;
                }
                if (mostRight1.right == null) {
                    mostRight1.right = cur1;
                    cur1 = cur1.left;
                } else {
                    mostRight1.right = null;
                    cur1 = cur1.right;
                }
            } else {
                cur = cur.right;
                cur1 = cur1.right;
            }

        }

        return cur == null && cur == cur1;

    }
}
